1. Field of the Invention
This invention relates to transform coding for digital signals, and more particularly to coding of audio signals or video signals.
2. Description of the Related Art
Conventionally, a linear transform coding system is known as a coding system for an audio or video signal. In the linear transform coding system, a plurality of samples obtained by sampling a signal are linearly transformed first and then coded, and depending upon a manner of selection of the base of the linear transform, compression coding can be achieved.
A best known transform coding system is discrete cosine transform (which may be hereinafter referred to simply as DCT) coding. It is known that the DCT achieves the highest compression coding of signals which conform to a highly correlated Markov maintenance model, and the DCT is utilized widely for international standardized systems. The DCT technique is disclosed in detail in K. R. Rao and P. Yip, "Discrete Cosine Transform Algorithms, Advantages, Applications", ACADEMIC PRESS, INC., 1990, translated into Japanese by Hiroshi Yasuda and Hiroshi Fujiwara, "Image Coding Technique", Ohm, 1992.
By the way, since the DCT is a transform which uses real numbers, coding (compression coding) by the DCT inevitably is non-reversible coding. In other words, lossless, reversible coding or distortion-free coding by which decoded signals accurately coincide with original signals is impossible with the DCT.
This will be described below with reference to FIG. 13 which illustrates a linear transform of a set of two digital signals.
Referring to FIG. 13, values which can be assumed by the original signals are represented as grating points on a two-dimensional space. Each of the grating points is called integer grating point of the original signals and is represented by a mark ".largecircle.". Each of the integer grating points is considered to represent a region (called integer cell) delineated by solid lines.
The original signals are linearly transformed and quantized into integral values with a suitable step. The linear transform can be regarded as a coordinate transform, and integer grating points of original signals are also arranged in a grating-like arrangement with a different inclination and/or a grating width. However, the grating points are displaced by conversion into integers or quantization in the transform region.
In FIG. 13, a quantization grating point in the transform region is indicated by a mark "x", and a quantization cell in the transform region is indicated by broken lines.
As seen from FIG. 13, for example, an integer point A of the original signals is quantized to another point B by the transform, and returns to the point A by an inverse transform. In other words, a reversible transform is realized.
However, another quantization point C of the original signals is quantized to a further point D and is displaced to a different point E by the inverse transform. Consequently, the transform in this instance is non-reversible transform. Besides, the point E is transformed to a different point F and then inversely transformed to another different point G. This signifies that repetitions of coding and decoding progressively increase the difference between the original image and the transformed image, or in other words, the error is accumulated.
This phenomenon can be eliminated by reducing the quantization step size after a transform. However, the reduction of the quantization step size yields transformed quantization points which will not be transformed, and this is a reverse effect from the point of view of compression coding.
The reversible coding is a desired technique for some application fields. The reversible coding is desired, for example, for a television system for a business use which repeats dubbing more than ten times after an original picture is imaged until it is broadcast.
Hadamard transform is known as an example of transform coding which realizes reversible coding. A two-element Hadamard transform and inverse transform are given by the following expressions (1) and (2), respectively: ##EQU1##
In the two-element Hadamard transform given above, since the integer vector (x1, x2) is transformed into another integer vector (y1, y2), full reversible coding is possible. A four-element or eight-element Hadamard transform can be defined using the two-element Hadamard transform recurrently and still allows full reversible coding.
However, the Hadamard transform described above is also a redundant transform.
As can be seen from the expressions (1) and (2) above, y1 is the sum of x1 and x2, and y2 is the difference between x1 and x2. Accordingly, if y1 is an even number, also y2 is an even number, but if y1 is an odd number, then also y2 is an odd number. In other words, one half ones of transformed quantization points are redundant points which are not used.
A method removing the redundancy of the Hadamard transform is already known.
For example, Japanese Patent Publication No. Heisei 2-62993 (title of the invention: "Coding and Decoding Apparatus for Pixel Signals") discloses a method of eliminating the redundancy using the relationship between an odd number and an even number after a transform.
However, for any other transform coding than the Hadamard transform, a coding system which realizes reversible coding and eliminates the redundancy to such a degree that the coding system can be used sufficiently for practical use of compression coding.
Particularly for a discrete cosine transform (DCT) which is known in that it is high in transform efficiency among various transform coding methods, no method of performing reversible coding is known.